package com.sheng.leetcode.year2022.month11.day24;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/11/24
 *<p>
 * 795. 区间子数组个数<p>
 *<p>
 * 给你一个整数数组 nums 和两个整数：left 及 right 。找出 nums 中连续、<p>
 * 非空且其中最大元素在范围 [left, right] 内的子数组，并返回满足条件的子数组的个数。<p>
 * 生成的测试用例保证结果符合 32-bit 整数范围。<p>
 *<p>
 * 示例 1：<p>
 * 输入：nums = [2,1,4,3], left = 2, right = 3<p>
 * 输出：3<p>
 * 解释：满足条件的三个子数组：[2], [2, 1], [3]<p>
 *<p>
 * 示例 2：<p>
 * 输入：nums = [2,9,2,5,6], left = 2, right = 8<p>
 * 输出：7<p>
 *<p>
 * 提示：<p>
 * 1 <= nums.length <= 10^5<p>
 * 0 <= nums[i] <= 10^9<p>
 * 0 <= left <= right <= 10^9<p>
 */
public class LeetCode0795 {

    @Test
    public void test01() {
//        int[] nums = {2,1,4,3};
//        int left = 2, right = 3;
        int[] nums = {2,9,2,5,6};
        int left = 2, right = 8;
        System.out.println(new Solution().numSubarrayBoundedMax(nums, left, right));
    }
}
class Solution {
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        /**
         * 思路：获取最大元素不超过 right 的子数组的个数，减去最大元素不超过 left - 1 的子数组的个数
         * 所获得的值即为，超过 left - 1的同时，不超过 right 的范围的子数组的个数
         */
        int ans = 0;
        // i 代表不超过 right 子数组的长度，i1 代表不超过 left - 1 的子数组的长度
        int i = 0, i1 = 0;
        // 循环数组
        for (int num : nums) {
            // 如果当前元素超过的限定范围，则将长度重置为 0 ，否则将长度加 1
            i = num > right ? 0 : i + 1;
            i1 = num > (left - 1) ? 0 : i1 + 1;
            ans += i - i1;
        }
        return ans;
    }
}
// 暴力破解，超时
//class Solution {
//    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
//        int length = nums.length;
//        int ans = 0;
//        // 循环数组
//        for (int i = 0; i < length; i++) {
//            int count = 0;
//            int max = nums[i];
//            if (max >= left && max <= right) {
//                // 满足范围
//                count++;
//            } else if (max > right) {
//                // 超出范围
//                continue;
//            }
//            int j = i + 1;
//            for (; j < length; j++) {
//                max = Math.max(max, nums[j]);
//                if (max >= left && max <= right) {
//                    count++;
//                } else if (max > right) {
//                    break;
//                }
//            }
//            // 跳过部分循环
//            if (count == 0) {
//                i = j;
//            }
//            // 累加
//            ans += count;
//        }
//        return ans;
//    }
//}
